{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Профилировка. Модель физической памяти."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[The Basics of Profiling - Mathieu Ropert - CppCon 2021](https://www.youtube.com/watch?v=dToaepIXW4s)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Уровни оптимизации компилятора"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "gcc / clang:\n",
    "\n",
    "https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* `-O0` - без оптимизаций (для отладки)\n",
    "* `-O1` - набор оптимизаций 1\n",
    "* `-O2` - набор оптимизаций 1 + набор оптимизаций 2\n",
    "* `-O3` - набор оптимизаций 1 + набор оптимизаций 2 + набор оптимизаций 3\n",
    "\n",
    "Чем выше `On`, тем больше время компиляции, но эффективнее код\n",
    "(чаще всего)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Дополнительные варианты:\n",
    "* `-Os` - сфокусироваться на оптимизации размера бинарного файла вместо скорости выполнения\n",
    "* `-Ofast` = `-O3` + `-ffast-math` - ослабить требования к математическим вычислениям - не выполнять все требования IEEE (может ускорить вычислительные алгоритмы, но программист должен быть уверен, что урезанных требований и меньшей точности достаточно)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Закинуть это код в godbolt, показать какой ассемблер генерирует компилятор для последнего gcc и clang на разных уровнях оптимизаций:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "#include <vector>\n",
    "\n",
    "int sum(const std::vector<int>& x)\n",
    "{\n",
    "    int rv = 0;\n",
    "    for (int v : x)\n",
    "        rv += v;\n",
    "    return rv;\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "msvc:\n",
    "\n",
    "https://docs.microsoft.com/en-us/cpp/build/reference/o-options-optimize-code?view=vs-2019"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Аналоги: `/Od`, `/O1`, `/O2`, `/Os` + доп. варинты (см. ссылку)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Профилировка на примере домашнего задания"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Visual studio:** Показать пример профилировки и просмотра результатов на msvc\n",
    "\n",
    "_(демонстрация)_"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<u>Замечание:</u> выполнять домашнее задание нужно на конфигурации `clang++-8  -stdlib=libc++ -O2 -std=c++17`.\n",
    "\n",
    "Чтобы установить clang и libc++ на ubuntu (если они ещё не установлены), выполните следующие команды:\n",
    "\n",
    "```sh\n",
    "sudo apt-get install clang-8\n",
    "sudo apt-get install libc++-dev\n",
    "sudo apt-get install libc++abi-dev\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**встроенный профилировщик в clang/gcc:**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Скрипт запуска встроенного в clang/gcc профилировщика:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```sh\n",
    "echo \"cleanup\"\n",
    "rm -f gmon.out analysis.txt .out\n",
    "\n",
    "echo \"compile\"\n",
    "clang++-8 -pg -O2 reference.cpp -stdlib=libc++ -std=c++17\n",
    "\n",
    "echo \"running\"\n",
    "./a.out\n",
    "\n",
    "echo \"analyze\"\n",
    "gprof a.out gmon.out > analysis.txt\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "_(демонстрация)_"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**google perf:**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Предустановки для инструмента google perf:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```sh\n",
    "sudo apt-get install google-perftools libgoogle-perftools-dev\n",
    "sudo apt-get install kcachegrind\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Прогон google perf:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```sh\n",
    "echo \"cleanup\"\n",
    "rm -f a.out cpu_profile callgrind\n",
    "\n",
    "echo \"compile\"\n",
    "clang++-8 -O2 reference.cpp -std=c++17 -stdlib=libc++\n",
    "\n",
    "echo \"run with profile\"\n",
    "LD_PRELOAD=/usr/lib/x86_64-linux-gnu/libprofiler.so CPUPROFILE=cpu_profile CPUPROFILE_FREQUENCY=5000 ./a.out\n",
    "\n",
    "echo \"analyze\"\n",
    "# google-pprof --gv   a.out cpu_profile  # X\n",
    "# google-pprof --web  a.out cpu_profile  # browser\n",
    "# google-pprof --text a.out cpu_profile  # console\n",
    "google-pprof --callgrind a.out cpu_profile > callgrind && kcachegrind callgrind\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "_(демонстрация)_"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Как настроить машину под измерение performance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Очистите ваш компьютер от стороннего софта настолько насколько это возможно (хотя бы на время замеров)\n",
    "    * Никаких баз данных\n",
    "    * Ваших личных крутящихся nginx\n",
    "    * Антивирусов\n",
    "    * Лишних демонов / сервисов\n",
    "    * Фоновых обновлений\n",
    "    * Чтения email-ов\n",
    "    * Открытых IDE\n",
    "* Вы должны быть единственным залогиненным пользователем на машине\n",
    "* В BIOS отключите Intel SpeedStep / SpeedShift / TurboBoost technologies\n",
    "    * сказать пару слов об этих технологиях и почему они влияют\n",
    "* [Disable hyper threading](https://www.pcmag.com/article/314585/how-to-disable-hyperthreading)\n",
    "    * сказать пару слов что такое hyper threading и почему он влияет\n",
    "* [Disable CPU scaling](https://askubuntu.com/questions/3924/disable-ondemand-cpu-scaling-daemon/3927) (linux, [doc](https://www.kernel.org/doc/Documentation/cpu-freq/governors.txt))\n",
    "* Disable [address space randomization](https://en.wikipedia.org/wiki/Address_space_layout_randomization)\n",
    "\n",
    "```sh\n",
    "echo 0 | sudo tee /proc/sys/kernel/randomize_va_space\n",
    "```\n",
    "\n",
    "* Ни в коем случае не запускайте измерялку из IDE (Visual Studio цепляется к программе и отслеживает её состояние), запускайте через консоль.\n",
    "* Привяжите процесс к ядру (лучше, ненулевому физ. ядру). Для linux есть команда `taskset`, в windows можно поковыряться в диспетчере.\n",
    "\n",
    "```sh\n",
    "taskset -c 2 ./a.out\n",
    "```\n",
    "* Измеряйте release-борку (O2 / O3).\n",
    "\n",
    "\n",
    "\n",
    "Для ознакомления:\n",
    "* https://easyperf.net/blog/2019/08/02/Perf-measurement-environment-on-Linux\n",
    "* https://github.com/ivafanas/sltbench/blob/master/doc/howtobenchmark.md"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Модель физической памяти"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Попытаемся ответить на вопрос, что происходит в железе, когда мы выполняем такой код, сколько тактов он работает:\n",
    "\n",
    "```c++\n",
    "int b = 5;\n",
    "\n",
    "...;\n",
    "\n",
    "int a = b + 3;  // b - переменная на стеке (предположим, компилятор во время оптимизаций её не выкинул)\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "_(Рисовать как дотянуть переменную `b` из RAM до регистров и зачем нужны кеши)_"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />\n",
    "<br />\n",
    "<br />\n",
    "<br />\n",
    "<br />\n",
    "<br />\n",
    "<br />\n",
    "<br />\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](mem_hierarchy_single_cpu.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Cache line**:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Когда данные идут из памяти в регистры через кеши, они идут блоками по (обычно) 64 байта. Этими же блоками они оседают в кешах памяти. Такой блок называется cache line.\n",
    "\n",
    "`64 byte == 8 x int64_t == 8 x double == 16 x int32_t == 16 x float`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Рассмотрим функцию, суммирующую элементы массива:\n",
    "\n",
    "```c++\n",
    "float sum(const std::vector<float>& v)\n",
    "{\n",
    "    float rv = 0;\n",
    "    for (float x : v)\n",
    "        rv += x;\n",
    "    return rv;\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "_(Рисовать как будут бегать данные между памятью и кешами для этой функции)_"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**За пределами рассказа**:\n",
    "* многопоточность и cache line-ы, разреженность\n",
    "* ассоциативность кешей\n",
    "* модель физической памяти NUMA"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Немного хардкорных ссылок:\n",
    "* [performance tuning guide for RHEL](https://access.redhat.com/documentation/en-us/red_hat_enterprise_linux/6/html/performance_tuning_guide/index)\n",
    "* [how to benchmark code time execution on Intel](https://www.intel.com/content/dam/www/public/us/en/documents/white-papers/ia-32-ia-64-benchmark-code-execution-paper.pdf)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Замечания после лекции:**\n",
    "* вставить скриншот `kcachegrind`-а чтобы показать, почему советую пользоваться именно им"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
